package com.lun.medium;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.lun.util.BinaryTree.TreeNode;

public class RecoverBinarySearchTree {

	// 方法一：我写的，用到中序遍历模式
	public void recoverTree(TreeNode root) {
		TreeNode p = root;
		LinkedList<TreeNode> stack = new LinkedList<>();
		List<TreeNode> candidates = new ArrayList<>();
		TreeNode prev = null;
		while (!stack.isEmpty() || p != null) {
			if (p != null) {
				stack.push(p);
				p = p.left;
			} else {
				TreeNode node = stack.pop();

				if (prev != null && prev.val >= node.val) {
					candidates.add(prev);
					candidates.add(node);
					if (candidates.size() == 4)
						break;
				}
				prev = node;
				p = node.right;
			}
		}

		TreeNode min = candidates.get(0), max = min;
		for (TreeNode node : candidates) {
			if (node.val < min.val)
				min = node;

			if (node.val > max.val)
				max = node;
		}
		int temp = min.val;
		min.val = max.val;
		max.val = temp;

	}

	// 方法二：方法一的改进
	public void recoverTree2(TreeNode root) {
		LinkedList<TreeNode> stack = new LinkedList<>();
		TreeNode first = null, second = null;
		TreeNode prev = null, curr = root;
		while (!stack.isEmpty() || curr != null) {
			if (curr != null) {
				stack.push(curr);
				curr = curr.left;
			} else {
				curr = stack.pop();

				if (prev != null && prev.val >= curr.val) {
					// incorrect smaller node is always found as prev node
					if (first == null)
						first = prev;
					// incorrect larger node is always found as curr node
					second = curr;
				}
				prev = curr;
				curr = curr.right;
			}
		}

		int temp = first.val;
		first.val = second.val;
		second.val = temp;
	}

	// 方法三：Morris遍历算法
	public void recoverTree3(TreeNode root) {
		TreeNode pre = null;
		TreeNode first = null, second = null;
		
		// Morris Traversal
		TreeNode temp = null;
		while (root != null) {
			if (root.left != null) {
				// connect threading for root
				temp = root.left;
				while (temp.right != null && temp.right != root)
					temp = temp.right;
				// the threading already exists
				if (temp.right != null) {
					
					if (pre != null && pre.val > root.val) {
						if (first == null) {
							first = pre;
						} 
						second = root;
					}
					pre = root;

					temp.right = null;
					root = root.right;
				} else {
					// construct the threading
					temp.right = root;
					root = root.left;
				}
			} else {
				
				if (pre != null && pre.val > root.val) {
					if (first == null) {
						first = pre;
					} 
					second = root;
				}
				
				pre = root;
				root = root.right;
			}
		}

		// swap two node values;
		if (first != null && second != null) {
			int t = first.val;
			first.val = second.val;
			second.val = t;
		}
	}

}
